Bandwidth allocation relates to the amount of bandwidth required by a connection (also referred to as a "virtual circuit") for the network to provide a required quality of service. Two alternative approaches to bandwidth allocation exist: deterministic multiplexing and statistical multiplexing.
Deterministic multiplexing allows each connection to reserve its peak bandwidth when the connection is established. As a result, deterministic multiplexing causes large amounts of bandwidth to be wasted for bursty connections, particularly those with large peak transmission rate to average transmission rate ratios. Also, deterministic multiplexing goes against the principles of networking technologies such as Asynchronous Transfer Mode (ATM), since deterministic multiplexing restricts the utilization of network resources.
Statistical multiplexing allocates an amount of bandwidth to a connection that is less than the peak rate, but greater than the average or minimum rate for that connection. With statistical multiplexing, the sum of the peak rates of connections multiplexed onto a link can be greater than the total link bandwidth. The bandwidth efficiency due to statistical multiplexing increases as the proportion of total bandwidth allocated to each connection approaches the average bit rate and decreases as it approaches the peak bit rate for each connection. In general, especially when network traffic is bursty in nature, statistical multiplexing allows more connections to be multiplexed onto a network link than deterministic multiplexing, thereby allowing better utilization of network resources.
In current ATM designs, rate based flow control is provided using the "leaky bucket" method. The standard leaky bucket method causes the link bandwidth to be effectively partitioned among to the multiple connections, similar to a deterministic multiplexing system. For example, where Req/T is the requested rate allocated to each connection, a leaky bucket scheme which guarantees Req/T bandwidth to N connections would require a total of Req * N/T bandwidth. During operation, if a given one of the N connections requested greater than Req/T bandwidth, the request for that bandwidth in excess of Req would be denied even if the given connection was the only connection active on the link. Thus the leaky bucket method does not allow for statistical multiplexing gains in bandwidth allocation.
An example of an existing system using a leaky bucket method for the multiplexing of connection bandwidth is now given. In the example of the existing system, there is total link rate of 100 megabits per second for use by the transmitting node over all connections with the receiving node. Also, there are multiple connections on the transmitting node for variable bit rate connections with the receiving node, each connection having requested a transmission rate of 10 megabits per second. The existing system allocates the requested data rate to each connection, effectively partitioning the bandwidth on the system among the connections, and providing a deterministic multiplexing system. The existing system would allow a maximum of 10 connections having a 10 megabit data rate to be connected with the receiving node.
The example existing system does not take into consideration the bursty nature of traffic on variable bit rate connections. If there are 10 connections having 10 megabits per second data rates, and if a transmit request were to arrive for a 20 megabit burst, the transmission data rate would be limited to 10 megabits per second, even if all nine other connections were silent at the time of the request.
For these reasons and others, there is therefore a need for a flow control system for networking technology such as ATM, including a system for bandwidth allocation, providing the advantages of statistical multiplexing of bandwidth for multiple connections over a network link.